<?php
/**
 * @title 97. 交错字符串 -
 * @author start2004
 */

class Solution {
    public $cachaArray;

    /**
     * @param String $s1
     * @param String $s2
     * @param String $s3
     * @return Boolean
     */
    function isInterleave($s1, $s2, $s3) {
        /**
         * @since 2021-07-12 长度
         */
        $len1 = strlen($s1);
        $len2 = strlen($s2);
        $len3 = strlen($s3);
        if($len1+$len2 != $len3){
            return false;
        } else {}

        /**
         * @since 2021-07-12 dp数组
         */
        $dpArray = array_fill(0, $len2+1, array_fill(0, $len1+1, 0));
        $dpArray[0][0] = 1;

        /**
         * @since 2021-07-12 第一行
         */
        for ($c=1; $c<=$len1; $c++){
            if($dpArray[0][$c-1] == 1 AND $s1[$c-1] == $s3[$c-1]){
                $dpArray[0][$c] = 1;
            } else {}
        }

        /**
         * @since 2021-07-12 第一列
         */
        for($r=1; $r<=$len2; $r++){
            if($dpArray[$r-1][0] == 1 AND $s2[$r-1] == $s3[$r-1]){
                $dpArray[$r][0] = 1;
            } else {}
        }
        // return $dpArray;

        /**
         * @since 2021-07-12 双循环
         */
        for ($r=1; $r<=$len2; $r++){
            for($c=1; $c<=$len1; $c++){
                /**
                 * @since 2021-07-12 dp[r][c-1] = 1 AND s1[c-1] = s3[r+c-1]
                 */
                // echo "r={$r}, c={$c}", PHP_EOL;
                // echo "dp[r][c-1]=", $dpArray[$r][$c-1], ", s1[c-1]=", $s1[$c-1], ", s3=[r+c-1]=", $s3[$r+$c-1], PHP_EOL;
                // echo "dp[r-1][c]=", $dpArray[$r-1][$c], ", s2[r-1]=", $s2[$r-1], ", s3=[r+c-1]=", $s3[$r+$c-1], PHP_EOL;
                // echo PHP_EOL;

                if($dpArray[$r][$c-1] == 1 AND $s1[$c-1] == $s3[$r+$c-1]){
                    $dpArray[$r][$c] = 1;
                } elseif($dpArray[$r-1][$c] == 1 AND $s2[$r-1] == $s3[$r+$c-1]) {
                    /**
                     * @since 2021-07-12 dp[r-1][c] = 1 AND s2[r-1] = s3[r+c-1]
                     */
                    $dpArray[$r][$c] = 1;
                } else {}
            }
        }
        // return $dpArray;

        /**
         * @return
         */
        return ($dpArray[$len2][$len1] == 1);
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.18_2.php
 */
$datas = [
    ["aabcc", "dbbca", "aadbbcbcac"],
    ["aabcc", "dbbca", "aadbbbaccc"],
    ["bbbbbabbbbabaababaaaabbababbaaabbabbaaabaaaaababbbababbbbbabbbbababbabaabababbbaabababababbbaaababaa", "babaaaabbababbbabbbbaabaabbaabbbbaabaaabaababaaaabaaabbaaabaaaabaabaabbbbbbbbbbbabaaabbababbabbabaab", "babbbabbbaaabbababbbbababaabbabaabaaabbbbabbbaaabbbaaaaabbbbaabbaaabababbaaaaaabababbababaababbababbbababbbbaaaabaabbabbaaaaabbabbaaaabbbaabaaabaababaababbaaabbbbbabbbbaabbabaabbbbabaaabbababbabbabbab"],

    ["aabc", "abad", "aabcabad"],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->isInterleave($data[0], $data[1], $data[2]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
